home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / p_aux_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.1 KB  |  90 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  p_aux_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PAIRING_AUX_HEAP_H
  17. #define LEDA_PAIRING_AUX_HEAP_H
  18.  
  19. #include <LEDA/impl/p_heap.h>
  20.  
  21. // by Markus Neukirch
  22. //
  23. // Implementation following John T. Stasko and Jeffrey Scott Vitter
  24. // ( Communications of the ACM   March 1987 Volume 30 Number 3   S. 234-240 )
  25.  
  26.  
  27.  
  28. class p_aux_heap:public p_heap
  29. {
  30.     
  31.     ph_item* head,*minptr;
  32.     int item_count;
  33.  
  34.     virtual int cmp(GenPtr x, GenPtr y) const {return compare (x,y);}
  35.  
  36.     virtual void print_key(GenPtr)  const {}
  37.     virtual void print_inf(GenPtr)  const {}
  38.  
  39.     virtual void clear_key(GenPtr&)  const {}
  40.     virtual void clear_inf(GenPtr&)  const {}
  41.     virtual void copy_key(GenPtr&)   const {}
  42.     virtual void copy_inf(GenPtr&)   const {}
  43.  
  44.     virtual int  int_type() const { return 0; }
  45.  
  46.     void do_copy(ph_item*,ph_item*,bool);
  47.     ph_item* twopass(ph_item*);
  48.     ph_item* multipass(ph_item*);
  49.     
  50. public:
  51.     
  52.     
  53.     p_aux_heap();
  54.  
  55.     p_aux_heap(int)     { error_handler(1,"no p_heap(int) constructor");}
  56.         p_aux_heap(int,int) { error_handler(1,"no p_heap(int,int) constructor");}
  57.  
  58.     p_aux_heap(const p_aux_heap& init);        // construct
  59.  
  60.     p_aux_heap& operator=(const p_aux_heap&);
  61.     ~p_aux_heap() {clear();}
  62.  
  63.     ph_item* insert(GenPtr,GenPtr);
  64.     void decrease_key(ph_item*,GenPtr);
  65.     ph_item* find_min() const
  66.         {return minptr;}
  67.     void delete_min_multipass();            // auxiliary version
  68.     void delete_min_twopass();            // auxiliary version
  69.  
  70.     GenPtr key(ph_item* x) const {return x->key;}
  71.     GenPtr inf(ph_item* x) const {return x->inf;}
  72.     
  73.     void change_inf(ph_item* x,GenPtr inf)
  74.         {clear_inf(x->inf);copy_inf(inf);x->inf=inf;}
  75.  
  76.     void del_item(ph_item* x)
  77.         {decrease_key(x,minptr->key);delete_min_twopass();}
  78.     
  79.     void clear() 
  80.         {p_heap::clear();item_count=0;}
  81.     int  size() const { return item_count;}
  82.     int  empty() const {return item_count;}
  83.  
  84.         
  85. };    
  86.  
  87.  
  88.  
  89. #endif
  90.